iT邦幫忙

2023 iThome 鐵人賽

DAY 21
0

https://ithelp.ithome.com.tw/upload/images/20231006/20149362bp07TOC59f.png
明天就是雙十連假了,我還在電腦前撰文
深呼吸告訴自己,是我要選參加鐵人賽的喔!是我!都是我


昨天討論到了陣列的 index 可以記錄資料在主記憶體中的位址,今天要來談跟它有點像的「鏈接串列

▌鏈接串列(Linked list)

「鏈接串列」中的元素(串列中的資料)可以被放在記憶體中的任何一個空位

「鏈接串列」在存放每個元素的同時,就會「紀錄下一個元素的存放位址」,所以能夠以「位址」依序找到每個串列中的「存取元素」,可以想成是我用地址找到你家。當今天我們要存一筆資料時,就必須要佔用到記憶體的空間,「鏈接串列」會依照記憶體中哪裡有空位,就把資料給塞進去,十分的彈性,塞進的位置有可能會在目前節點的前方或後方

在上一篇我們可以發現 C 語言在宣告陣列時,需要先指定每列和每行有幾個元素,也就是你得需要知道資料的大小,但這樣其實要動態新增、刪除元素時,是件很麻煩的事,但「鏈接串列」就不需要遵守這個規則

▪ 鏈接串列的特點:

  • 是由一個個節點(Node)所組成的,每個節點的tpye不必相同
  • 每一個節點裡會存下一個節點的指標(Pointer)
  • 不按照順序排列、儲存(非連續)
  • 充分利用電腦記憶體空間
  • 新增、刪除元素很方便,彈性度高
  • 存取速度比陣列慢,因要先讀取指標
  • 並非所有程式語言都有,像JS就沒有內建 Linked List,可以使用這個 link list 第三方套件擴充

▪ 什麼時候適合使用鏈接串列?

資料存取的方式有兩種

  • 依序存取(Sequential Access): 也是逐一存取,依照第一個元素開始依序存取
  • 隨機存取(Random Access):依照資料的「index」 來存取

看到這應該可以猜想到鏈接陣列是哪一從存取方式了
那就是「依序存取」!

假設今天我們要存取鏈結串列的第五個元素,必須要先依序訪問前面四個元素,得到節點指標後,才能找到第五個元素

所以「鏈接串列」的使用時機是需要「逐一存取元素」時!讀取一個元素後,再依照位址讀取下一個元素,如果沒有要依序讀取,可以選擇使用「陣列」Array。此外,鏈結串列也會用來構建許多其它資料結構,像是之後會提到的堆疊(Stack),佇列(Queue)等(這是非常重要的觀念,前端面試中很常考)

P.S 陣列就是「隨機存取」,在實務上的應用比較廣

▌資料的操作 - 新增

這裡先拿自己比較熟悉的JS舉例

const foodList = ['pasta', 'coffee', 'pizza', 'chocolate']

https://ithelp.ithome.com.tw/upload/images/20231007/201493627hH7GWK0AQ.png
如果你今天想要在 'coffee' 和 'pizza' 中間插入 'shushi',你會選用「陣列」還是「鏈接串列」?

答案是「鏈接串列」!!
原因是如果選用陣列,就必須要在插入 'shushi' 後的所以元素都往後移,如果沒有記憶體空間可以移,就必須換到其他位子,十分的麻煩。用「鏈接串列」只需要修改前一個元素(也就是'coffee' )中記錄的下一個節點指標即可

突然覺得「陣列」、「鏈接串列」分別有點像一般筆記本和活頁式筆記本,一般筆記本頁數都是固定的,也代表書寫空間有限,今天突然心血來潮想在某頁之間插入新頁是很麻煩的!但是活頁式就可以看我想在哪新增就在哪,方便許多

▌資料的操作 - 刪除

https://ithelp.ithome.com.tw/upload/images/20231007/20149362igoiwZdbQA.png
如果你今天想要把 'pizza' 移除,你會選用「陣列」還是「鏈接串列」?

答案還是「鏈接串列」
因為只要修改前一個節點中所存下的節點指標就可以了!反觀「陣列」在刪除 'pizza' 後,還要把後面的所有元素我前挪動。與「新增」不同的是,「刪除」並不會遇到「記憶體空間不足」而失敗的問題

▌總結

「鏈接串列」和「陣列」有一個很大的不同,就是鏈接串列的「邏輯順序」和「實體順序」可能不同,也就是它的 index 不一定是 0, 1, 2... 由小到大排列,因其不連續性,我們可利用「鏈接串列」來儲存不確定大小或會動態刪減的資料,以下是「陣列」和「鏈接串鍊」的比較表

陣列 鏈接串鍊
佔用記憶體連續的空間 記憶體空間不連續
各元素型態皆需相同 各節點型態可不相同
增刪元素較為麻煩 增刪元素較為方便
隨機隨取(應用較廣) 只能用依序存取(應用叫狹隘)
可靠度高 可靠度低,只要指標斷裂,資料就沒了

▌參考資料

  1. 白話演算法!Aditya Y. Bhargava 著
  2. wikipedia

上一篇
Day20 | 資料結構:陣列 Array
下一篇
Day 22 | 樹狀結構 (Tree) - 你要了解的節點觀念
系列文
來場計概入門課吧X資訊人該了解的通識素養31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言